package com.zh.note.leetcode.backtracking;

import java.util.ArrayList;
import java.util.List;

/**
 * 93. 复原 IP 地址
 * <p>
 * 示例 1：
 * <p>
 * 输入：s = "25525511135"
 * 输出：["255.255.11.135","255.255.111.35"]
 */
public class LC_93_restoreIpAddresses {


    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();
        dfs(s, 0, 0, res);
        return res;

    }

    // startIndex: 搜索的起始位置， pointNum:添加逗点的数量
    private void dfs(String s, int startIndex, int pointNum, List<String> res) {
        if (pointNum == 3) {
            //对最后一段进行合法性判断 [startIndex, s.length() - 1]
            if (isValid(s, startIndex, s.length() - 1)) {
                res.add(s);
                return;
            }
        }
        for (int i = startIndex; i < s.length(); i++) {
            if (isValid(s, startIndex, i)) { // 判断 [startIndex,i] 这个区间的子串是否合法
                s = s.substring(0, i + 1) + "." + s.substring(i + 1);   // 在i的后面插入一个逗点
                pointNum += 1;
                dfs(s, i + 2, pointNum, res); // 插入逗点之后下一个子串的起始位置为i+2
                pointNum -= 1;
                s = s.substring(0, i + 1) + s.substring(i + 2); // 回溯删掉逗点
            } else {
                break; // 不合法，直接结束本层循环
            }
        }
    }

    private boolean isValid(String s, int start, int end) {
        if (start > end) {
            return false;
        }
        //首位不能是0
        if (s.charAt(start) == '0' && start != end) {
            return false;
        }
        int num = 0;
        // 必须是数字
        for (int i = start; i <= end; i++) {
            if (s.charAt(i) > '9' && s.charAt(i) < '0') {
                return false;
            }
            num = num * 10 + (s.charAt(i) - '0');
            if (num > 255) { // 如果⼤于255了不合法
                return false;
            }
        }
        return true;
    }

}
